package pers.qianyu.month_202012.date_20201204;

import org.junit.*;
import pers.qianyu.util.*;

import java.util.*;

/**
 * 45. 跳跃游戏 II
 * https://leetcode-cn.com/problems/jump-game-ii/
 *
 * @author mizzle rain
 * @date 2020-12-03 23:41
 */
public class Jump2 {
    public int jump(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        int[] dp = new int[nums.length];
        for (int i = 1, last = 0; i < dp.length; i++) {
            while (last < dp.length && last + nums[last] < i) {
                last++;
            }
            dp[i] = dp[last] + 1;
        }
        return dp[dp.length - 1];
    }

    public int jump2(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
            System.out.println("i:" + i + " end:" + end +
                    " maxPosition:" + maxPosition + " steps:" + steps);
        }
        return steps;
    }

    @Test
    public void test1() {
        int[] param = {2, 3, 1, 1, 4};
        ArrayUtil.printIndex(param.length);
        System.out.println(Arrays.toString(param));
        int result = new Jump2().jump2(param);
        System.out.println("result = " + result);
    }
}
